#include <ut/UnitTest.h>
#include <illib/Log.h>
#include <illib/System.h>
#include <illib/BasicRedBlackTree.h>
#include <illib/Exception.h>
#include <limits>

using namespace illib;

namespace illib_ut{
	class SingleTestNode : public BasicRedBlackTree::Node{
	public:
		SingleTestNode() :
			number_(0)
		{

		}
		SingleTestNode(uint32_t number) :
			number_(number)
		{

		}
		uint32_t number_;
	};
	class SingleTestTreeFunctions : public BasicRedBlackTree::TreeFunctions {
	public:
		virtual bool lesser(BasicRedBlackTree::Node &left, BasicRedBlackTree::Node &right){
			SingleTestNode * leftNode = static_cast<SingleTestNode*>(&left);
			SingleTestNode * rightNode = static_cast<SingleTestNode*>(&right);
			bool result = (leftNode->number_ < rightNode->number_);
			//Console::print("Left %d Right < %d [%d]\n", leftNode->number_,rightNode->number_, result);
			return result;
		}
		virtual bool greater(BasicRedBlackTree::Node &left, BasicRedBlackTree::Node &right){
			SingleTestNode * leftNode = static_cast<SingleTestNode*>(&left);
			SingleTestNode * rightNode = static_cast<SingleTestNode*>(&right);
			bool result = (leftNode->number_ > rightNode->number_);
			//Console::print("Left %d Right > %d [%d]\n", leftNode->number_,rightNode->number_, result);
			return result;
		}
		virtual bool equal(BasicRedBlackTree::Node &left, BasicRedBlackTree::Node &right){
			SingleTestNode * leftNode = static_cast<SingleTestNode*>(&left);
			SingleTestNode * rightNode = static_cast<SingleTestNode*>(&right);
			bool result = (leftNode->number_ == rightNode->number_);
			//Console::print("Left %d Right == %d [%d]\n", leftNode->number_,rightNode->number_, result);
			return result;
		}
	};
	class RangeTestNode : public BasicRedBlackTree::Node{
	public:
		RangeTestNode(uint32_t start, uint32_t size) :
			start_(start),
			size_(size)
		{

		}
		RangeTestNode() :
			start_(0),
			size_(0)
		{

		}
		uint32_t start_;
		uint32_t size_;
	};
	class RangeTestTreeFunctions : public BasicRedBlackTree::TreeFunctions {
	public:
		virtual bool lesser(BasicRedBlackTree::Node &left, BasicRedBlackTree::Node &right){
			RangeTestNode * leftNode = static_cast<RangeTestNode*>(&left);
			RangeTestNode * rightNode = static_cast<RangeTestNode*>(&right);
			uint32_t leftStart = leftNode->start_;
			uint32_t rightStart = rightNode->start_;
			uint32_t leftEnd = leftNode->start_ + leftNode->size_;
			uint32_t rightEnd = rightNode->start_ + rightNode->size_;
			bool result = ((leftStart < rightStart) && (leftEnd < rightEnd));
			//Console::print("Left %d:%d < Right %d:%d [%d]\n", leftStart,leftEnd,rightStart,rightEnd, result);
			return result;
		}
		virtual bool greater(BasicRedBlackTree::Node &left, BasicRedBlackTree::Node &right){
			RangeTestNode * leftNode = static_cast<RangeTestNode*>(&left);
			RangeTestNode * rightNode = static_cast<RangeTestNode*>(&right);
			uint32_t leftStart = leftNode->start_;
			//uint32_t rightStart = rightNode->start_;
			//uint32_t leftEnd = leftNode->start_ + leftNode->size_;
			uint32_t rightEnd = rightNode->start_ + rightNode->size_;
			bool result = (leftStart > rightEnd);
			//Console::print("Left %d:%d > Right %d:%d [%d]\n", leftStart,leftEnd,rightStart,rightEnd, result);
			return result;
		}
		virtual bool equal(BasicRedBlackTree::Node &left, BasicRedBlackTree::Node &right){
			RangeTestNode * leftNode = static_cast<RangeTestNode*>(&left);
			RangeTestNode * rightNode = static_cast<RangeTestNode*>(&right);
			uint32_t leftStart = leftNode->start_;
			uint32_t rightStart = rightNode->start_;
			uint32_t leftEnd = leftNode->start_ + leftNode->size_;
			uint32_t rightEnd = rightNode->start_ + rightNode->size_;
			bool result = ((leftStart >= rightStart) && (leftEnd <= rightEnd));
			//Console::print("Left %d:%d == Right %d:%d [%d]\n", leftStart,leftEnd,rightStart,rightEnd, result);
			return result;
		}
	};

	void BasicRedBlackTree_ut() {
		ut::UnitTestLogger logger(TN(illib_ut::BasicRedBlackTree_ut));
		{
			SingleTestTreeFunctions functions;
			BasicRedBlackTree::Tree tree;

			/*const size_t count1 = 200;
			SingleTestNode nodes1[count1];
			for(uint32_t i = 0; i < count1; i++){
				nodes1[i].number_ = i*20+400;
				tree.add(nodes1[i]);
			}*/

			SingleTestNode m5(100);
			tree.add(m5, functions);
			SingleTestNode m1(20);
			tree.add(m1, functions);
			SingleTestNode m2(40);
			tree.add(m2, functions);
			SingleTestNode m6(120);
			tree.add(m6, functions);
			SingleTestNode m3(60);
			tree.add(m3, functions);
			SingleTestNode m4(80);
			tree.add(m4, functions);

			/*const size_t count2 = 100;
			SingleTestNode nodes2[count2];
			for(uint32_t i = 0; i < count2; i++){
				nodes2[i].number_ = i+101;
				tree.add(nodes2[i]);
			}*/

			{
				//Console::print("find positive forward 80\n");
				SingleTestNode f(80);
				BasicRedBlackTree::Iterator i(f, tree, functions, true);
				ut::test(AT(), EX(i.current() != 0), TN(BasicRedBlackTree::Iterator::current));
				ut::test(AT(), EX(static_cast<SingleTestNode*>(i.current())->number_ == f.number_), TN(BasicRedBlackTree::Iterator::current));
			}

			{
				//Console::print("find positive reverse 80\n");
				SingleTestNode f(80);
				BasicRedBlackTree::Iterator i(f, tree, functions, false);
				ut::test(AT(), EX(i.current() != 0), TN(BasicRedBlackTree::Iterator::current));
				ut::test(AT(), EX(static_cast<SingleTestNode*>(i.current())->number_ == f.number_), TN(BasicRedBlackTree::Iterator::current));
			}

			{
				//Console::print("find negative forward 70\n");
				SingleTestNode f(70);
				BasicRedBlackTree::Iterator i(f, tree, functions, true);
				ut::test(AT(), EX(i.current() == 0), TN(BasicRedBlackTree::Iterator::current));
			}

			{
				//Console::print("find negative reverse 70\n");
				SingleTestNode f(70);
				BasicRedBlackTree::Iterator i(f, tree, functions, false);
				ut::test(AT(), EX(i.current() == 0), TN(BasicRedBlackTree::Iterator::current));
			}

			{
				//Console::print("iterate forward\n");
				BasicRedBlackTree::Iterator i(tree, functions, true);
				ut::test(AT(), EX(i.current() != 0), TN(BasicRedBlackTree::Iterator::current));
				uint32_t n = 0;
				while(i.current()){
					ut::test(AT(), EX(static_cast<SingleTestNode*>(i.current())->number_ > n), TN(BasicRedBlackTree::Iterator::current));
					n = static_cast<SingleTestNode*>(i.current())->number_;
					i.next();
				}
			}

			{
				//Console::print("iterate reverse\n");
				BasicRedBlackTree::Iterator i(tree, functions, false);
				ut::test(AT(), EX(i.current() != 0), TN(BasicRedBlackTree::Iterator::current));
				uint32_t n = std::numeric_limits<uint32_t>::max();
				while(i.current()){
					ut::test(AT(), EX(static_cast<SingleTestNode*>(i.current())->number_ < n), TN(BasicRedBlackTree::Iterator::current));
					n = static_cast<SingleTestNode*>(i.current())->number_;
					i.next();
				}
			}

			{
				//Console::print("find positive forward 50\n");
				SingleTestNode s(50);
				SingleTestNode e(100);
				BasicRedBlackTree::Iterator i(s, e, tree, functions, true);
				ut::test(AT(), EX(i.current() != 0), TN(BasicRedBlackTree::Iterator::current));
				uint32_t n = 0;
				while(i.current()){
					ut::test(AT(), EX(static_cast<SingleTestNode*>(i.current())->number_ > s.number_), TN(BasicRedBlackTree::Iterator::current));
					ut::test(AT(), EX(static_cast<SingleTestNode*>(i.current())->number_ <= e.number_), TN(BasicRedBlackTree::Iterator::current));
					ut::test(AT(), EX(static_cast<SingleTestNode*>(i.current())->number_ > n), TN(BasicRedBlackTree::Iterator::current));
					n = static_cast<SingleTestNode*>(i.current())->number_;
					i.next();
				}
			}

			{
				//Console::print("find positive reverse 50\n");
				SingleTestNode s(50);
				SingleTestNode e(100);
				BasicRedBlackTree::Iterator i(s, e, tree, functions, false);
				ut::test(AT(), EX(i.current() != 0), TN(BasicRedBlackTree::Iterator::current));
				uint32_t n = std::numeric_limits<uint32_t>::max();
				while(i.current()){
					ut::test(AT(), EX(static_cast<SingleTestNode*>(i.current())->number_ > s.number_), TN(BasicRedBlackTree::Iterator::current));
					ut::test(AT(), EX(static_cast<SingleTestNode*>(i.current())->number_ <= e.number_), TN(BasicRedBlackTree::Iterator::current));
					ut::test(AT(), EX(static_cast<SingleTestNode*>(i.current())->number_ < n), TN(BasicRedBlackTree::Iterator::current));
					n = static_cast<SingleTestNode*>(i.current())->number_;
					i.next();
				}
			}
		}
		{
			RangeTestTreeFunctions functions;
			BasicRedBlackTree::Tree tree;

			const size_t count1 = 200;
			RangeTestNode nodes1[count1];
			for(uint32_t i = 0; i < count1; i++){
				nodes1[i].start_ = (i*20)+400;
				nodes1[i].size_ = 10;
				tree.add(nodes1[i], functions);
			}

			RangeTestNode m5(100,10);
			tree.add(m5, functions);
			RangeTestNode m1(20,10);
			tree.add(m1, functions);
			RangeTestNode m2(40,10);
			tree.add(m2, functions);
			RangeTestNode m6(120,10);
			tree.add(m6, functions);
			RangeTestNode m3(60,10);
			tree.add(m3, functions);
			RangeTestNode m4(80,10);
			tree.add(m4, functions);

			const size_t count2 = 100;
			RangeTestNode nodes2[count2];
			for(uint32_t i = 0; i < count2; i++){
				nodes2[i].start_ = (i*10)+101;
				nodes2[i].size_ = 5;
				tree.add(nodes2[i], functions);
			}
			{
				//Console::print("find positive forward range 85\n");
				RangeTestNode f(85,0);
				BasicRedBlackTree::Iterator i(f, tree, functions, true);
				ut::test(AT(), EX(i.current() != 0), TN(BasicRedBlackTree::Iterator::current));
			}
			{
				//Console::print("find positive reverse range 85\n");
				RangeTestNode f(85,0);
				BasicRedBlackTree::Iterator i(f, tree, functions, false);
				ut::test(AT(), EX(i.current() != 0), TN(BasicRedBlackTree::Iterator::current));
			}
		}
	}
};
